Section: New Results

Automatic decomposition of discretized surfaces for parallel processing

Participants : S.H. Lo, H. Borouchaki [correspondant], P. Laug

Free-form surfaces and industrial surface forms could nowadays be conveniently generated efficiently by laser-based digitizing techniques or from a CAD graphics system. Automatic algorithms are imperative to decompose complex triangulated objects consisting of thousands to millions of nodal points into simpler surface parts for parameterization and parallel processing. Non-manifold complicated discretized objects will be handled and simple closed or open surface parts (manifolds) are retrieved by means of pure topological considerations. Each of the simple surface part, which is topologically equivalent to an open surface, a sphere or a torus will be decomposed by entirely topological operations into n equal pieces based on a specified geometrical criterion such as surface area, Gaussian curvatures or magnitudes of dihedral angles, etc. Cut planes could be conveniently defined normal to the axes of inertia of the object to be decomposed. The cut plane which produces surface parts which best respect the given criterion will be chosen, and the two bisected surfaces will be made as equal as possible by means of some general balancing mechanisms. This procedure could be repeated as often as necessary until sub-surface parts satisfying the given criterion are obtained. Each piece of the decomposed surfaces having an intact topological boundary can then be processed independently in parallel, and all the pieces could be put back together to recover the original object or partially to represent a certain portion of the object [29] .